04 Clustering

Unit 1: Vectors, Book ILA Ch. 1-5

• 01 Vectors
• 02 Linear Functions
• 03 Norms and Distances
• 04 Clustering
• 05 Linear Independence

Unit 2: Matrices, Book ILA Ch. 6-11 + Book IMC Ch. 2

Unit 3: Least Squares, Book ILA Ch. 12-14 + Book IMC Ch. 8

Unit 4: Eigen-decomposition, Book IMC Ch. 10, 12, 19

Outline: 04 Clustering

• Clustering
• Algorithm
• Examples
• Applications

Outline: 04 Clustering

• Clustering
• Algorithm
• Examples
• Applications

Clustering in Machine Learning

Clustering: Goal (Intuition)

• Given: (i) dataset of $N$ $n$-vectors $x_1, . . . , x_N$, (ii) integer $k$,
• $\color{#EF5645}{\text{Goal (Intuition)}}$:
  • Partition/Group/Cluster $N$ vectors into $k$ groups/clusters...
  • ... such that: vectors in the same group are "close".

$\color{#047C91}{\text{Exercise}}$: What is $k$ in the figure above? What is $n$? What is $N$?

Clustering in ECE

• topic discovery and document clustering
  • $x_i$ is word count vector for document $i$
• patient clustering
  • $x_i$ are patient attributes, test results, symptoms for patient $i$
• customer market "segmentation"
  • $x_i$ is purchase history and other attributes of customer $i$
• financial sectors
  • $x_i$ are $n$-vectors of financial attributes of company $i$

Clustering: Goal (Math)

• $\color{#EF5645}{\text{Notations}}$:

  • Group $G_j$ for $j=1, ..., k$: Set of indices in $1, ..., N$ representing which vectors belong to the group.
  • Assignment $c_i$ for $i=1,...,k$: Group that $x_i$ is in: $i \in G_{c_i}$
  • Group representative $z_j$ for $j=1, ..., k$: $n$-vector that represents a typical element of the group $G_j$.

• $\color{#EF5645}{\text{Goal (Math)}}$: Find $c_i$ and $z_j$ to minimize $J^{clust} = \frac{1}{N}\sum_{i=1}^N ||x_i - z_{c_i}||^2$ , i.e. the mean square distance from vectors to their representatives.

Outline: 04 Clustering

• Clustering
• Algorithm
• Examples
• Applications

K-means algorithm

• Alternate between:

  • (i) update the groups, i.e the group assignments $c_1, ..., c_N$,
  • (ii) update the representatives $z_1, ..., z_k$.

• Such that the objective $J^{clust}$ decreases at each step.

(i) Update the groups

• Given: representatives $z_1, ..., z_k$
• $\color{#EF5645}{\text{Goal for (i)}}$: Assign vectors to groups, i.e. choose $c_1, ..., c_N$
  • We assign each vector to its nearest representative. Justification:
    • Observe: $c_i$ only appears in term $||x_i - z_{c_i}||^2$ in $J^{clust}$
    • Conclude: to minimize over $c_i$, choose $c_i$ so $‖x_i − z_{c_i} ‖^2 = min_{j \in \{1, ..., k\}} ‖x_i − z_j ‖^2$.

(ii) Update the representatives

• Given the partition $G_1, . . . , G_k$
• $\color{#EF5645}{\text{Goal for (ii)}}$: Choose representatives $z_1, . . . , z_k$
  • Choose $z_j$ = mean of the points in group $j$. Justification:
    • Observe: $J^{clust}$ splits into a sum of $k$ sums: $$J^{clust} = J_1 + · · · + J_k, \quad J_j = \frac{1}{N} \sum_{i \in G_j} ‖x_i − z_j ‖^2.$$
    • Conclude: Choose $z_j$ to minimize its $J_j$: $z_j = \frac{1}{|G_j|} \sum_{i \in G_j} x_i$ = mean/center/centroid.

Pseudo-code

Convergence of K-means

• How many times do we iterate these steps?
  • Until the $z_j$’s stop changing: "convergence" of the algorithm.

• $\color{#EF5645}{\text{Remarks}}$:

  • $J^{clust}$ decreases at each step,
  • but in general we don't find partition that minimizes $J^{clust}$,
  • the final partition depends on initial representatives.

• $\color{#EF5645}{\text{Recommendation}}$:

  • Run $k$-means 10 times, with different initial representatives
  • Take as final partition the one with smallest $J^{clust}$

Outline: 04 Clustering

• Clustering
• Algorithm
• Example
• Applications

Outline: 04 Clustering

• Clustering
• Algorithm
• Examples
• Applications

MNIST Dataset: Find Digits

• MNIST images of handwritten digits (via Yann Lecun)
• $60, 000$ images of size 28 × 28, represented as 784-vectors $x_i$

• $\color{#EF5645}{\text{Goal}}$: Group these images into groups of same digit.
• $\color{#047C91}{\text{Exercice}}$: What are $k, N, n$?

MNIST Results

Convergences: best run (blue), worst run (red), average (brown).

Representatives.

Wikipedia Dataset: Find Topics

• Wikipedia articles
• 500 articles, where the word count vectors are computed (dictionary of 4423 words)

• $\color{#EF5645}{\text{Goal}}$: Group these articles into groups of same topic.
• $\color{#047C91}{\text{Exercice}}$: What are $k, N, n$?

Wikipedia Results

Convergences: best run (blue), worst run (red), average (brown).

Explore first 3 clusters.

• words with largest representative coefficients

• titles of articles closest to cluster representative

Questions?

• Clustering
• Algorithm
• Examples
• Applications

Resources: Book ILA, Ch. 4